package oj;

import java.util.ArrayList;
import java.util.List;

//杨辉三角：给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。在「杨辉三角」中，每个数是它左上方和右上方的数的和。
public class Solution_118 {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ans = new ArrayList<>();
        //没有元素
        if(numRows == 0){
            return ans;
        }
        //只有一行：[[1]]
        ans.add(new ArrayList<>());
        ans.get(0).add(1);
        if(numRows == 1){
            return ans;
        }
        //只有两行：[[1],[1,1]]
        ans.add(new ArrayList<>());
        ans.get(1).add(1);
        ans.get(1).add(1);
        if(numRows == 2){
            return ans;
        }
        //大于三行
        for(int i = 3;i <= numRows;i++){
            //需要多增加一行
            List<Integer> curLine = new ArrayList<>();
            ans.add(curLine);
            ans.get(i - 1).add(1);
            for(int j = 0;j < i - 2;j++){
                //j=0 的时候计算该行的第 2 个元素，由上一行的第 1 个元素和第 2 个元素相加得到
                //j=1 的时候计算该行的第 3 个元素，由上一行的第 2 个元素和第 3 个元素相加得到
                //j 的时候计算该行的第 j + 2 个元素，由上一行的第 j + 1 个元素和第 j + 2 个元素相加得到
                //下标都统一 - 1
                List<Integer> prevLine = ans.get(i - 2);
                int first = prevLine.get(j);
                int second = prevLine.get(j + 1);
                int e = first + second;
                curLine.add(e);
            }
            curLine.add(1);
        }
        return ans;
    }

    public static void main(String[] args) {
        Solution_118 solution_118 = new Solution_118();
        System.out.println(solution_118.generate(0));
        System.out.println(solution_118.generate(1));
        System.out.println(solution_118.generate(2));
        System.out.println(solution_118.generate(3));
        System.out.println(solution_118.generate(4));
        System.out.println(solution_118.generate(5));

    }
}
